#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <stdlib.h>
#include<math.h>
//double fx(int a, int b, int e)
//{
//
//	while (e <= b)
//	{
//		int c = 1;
//		for (int k = 1; k <= e; k++)
//		{
//			c = c * a;
//		}
//		double x = e / c;
//		return x + fx(a, b, e + 1);
//	}
//}
//int main()
//{
//	int a, b;
//	int e = 1;
//	scanf("%d%d", &a, &b);
//	double ret = fx(a, b, e);
//	printf("%.3lf", ret);
//	return 0;
//}
//
//int arr2[10];
//int main()
//{
//	int a = 0;
//	int arr[3] = { 3,0,1 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	for (int i = 0; i < sz; ++i)
//	{
//		a ^= arr[i];
//	}
//	printf("%d\n", a);
//	for (int i = 0; i <= sz; ++i)
//	{
//		a ^= i;
//	}
//	printf("%d\n", a);
//	return 0;
//}
//
//void print(int n)
//{
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			printf("%3d", i*j);
//		}
//		printf("\n");
//	}
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	print(n);
//	return 0;
//}
//
//void swap(int* pa, int* pb)
//{
//	int tmp = *pa;
//	*pa = *pb;
//	*pb = tmp;
//}
//int main()
//{
//	int a, b;
//	scanf("%d%d", &a, &b);
//	printf("%d %d\n", a, b);
//	swap(&a, &b);
//	printf("%d %d\n", a, b);
//	return 0;
//}
//
//void is_the_year(int a)
//{
//	if (a % 4 == 0 && a % 100 != 0 || a % 400 == 0)
//	{
//		printf("yes");
//	}
//	else
//		printf("no");
//}
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	is_the_year(a);
//	return 0;
//}
//
//void is_prime_number(int a)
//{
//	int flag = 1;
//	for (int i = 2; i < sqrt(a); i++)
//	{
//		if (a % i == 0)
//		{
//			flag = 0;
//		}
//	}
//	if (flag == 0)
//	{
//		printf("no");
//	}
//	else
//		printf("yes");
//}
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	is_prime_number(a);
//	return 0;
//}
//
//int k_capital(int x, int k)
//{
//	if (k == 0)
//		return 1;
//	else
//		return x * k_capital(x, k - 1);
//}
//int main()
//{
//	int x,k;
//	scanf("%d %d", &x, &k);
//	printf("%d",k_capital(x, k));
//	return 0;
//}
//
//int sum(int a)
//{
//
//	if (a < 9)
//		return a;
//	else
//		return a % 10 + sum(a / 10);
//}
//int main()
//{
//	int val;
//	scanf("%d", &val);
//	int ret=sum(val);
//	printf("%d", ret);
//	return 0;
//}
//
////int Strlen(char* str)
////{
////	if (*str != '\0') 
////	{
////	return 1+Strlen(++str);
////	}
////	else
////	{
////		return 0; 
////	}
////		
////}
//int Strlen(char* str)
//{
//	int count = 0;
//	while (*str != '\0')
//	{
//		count++;
//		str++;
//	}
//	return count;
//}
//int main()
//{
//	char arr[] = "abcdef";
//	int ret = Strlen(arr);
//	printf("%d", ret);
//	return 0;
//}
//
//void Print(int a)
//{
//	if (a < 9)
//		printf("%2d", a);
//	else
//	{
//		Print(a / 10);
//		printf("%2d", a % 10);
//	}
//}
//int main()
//{
//	int a;
//	scanf("%d", &a);
//	Print(a);
//	return 0;
//}
//
//int fib(int n)
//{
//	if (n <= 2)
//		return 1;
//	else
//		return fib(n - 1) + fib(n - 2);
//}
//int fib(int n)
//{
//	int a = 1;
//	int	b = 1;
//	int c = 0;
//	for (int i = 0; i < n-2; i++)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//	}
//	return c;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	int ret = fib(n);
//	printf("%d", ret);
//	return 0;
//}

//int Strlen(char* str)
//{
//	int count = 0;
//	while (*str != '\0')
//	{
//		str++;
//		count++;
//	}
//	return count;
//}
////void reveser(char* str)
////{
////	int len = Strlen(str);
////	int left = 0;
////	int right = len - 1;
////	int tmp = 0;
////	while (left < right)
////	{
////		tmp = *(str + left);
////		*(str + left) = *(str + right);
////		*(str + right) = tmp;
////		left++;
////		right--;
////	}
////}
//void reveser(char* str)
//{
//	int len = Strlen(str);
//	char tmp = *str;
//	*str = *(str + len - 1);
//	*(str + len - 1) = '\0';
//	if(Strlen(str+1)>=2)
//		reveser(str+1);
//	
//	*(str + len - 1) = tmp;
//}
//int main()
//{
//	char arr[] = { "abcdef" };
//	int len = Strlen(arr);
//	printf("%s\n", arr);
//	reveser(arr,len);
//	printf("%s\n",arr);
//	return 0;
//}
//
//int powe(int n,int k)
//{
//	int pow = 1;
//	if (k == 0)
//		return 1;
//	else
//		for (int i = 0; i < k; i++)
//		{
//			pow *= n;
//		}
//	return pow;
//}
//int powe(int n, int k)
//{
//	if (k == 0)
//		return 1;
//	else
//		return n* powe(n, k - 1);
//}
//int main()
//{
//	int n;
//	int k;
//	scanf("%d%d", &n, &k);
//	int ret = powe(n, k);
//	printf("%d\n",ret);
//	return 0;
//}
//